package java;

import java.util.ArrayList;
import java.util.List;

public class Question22 {
    public static void main(String[] args) {
        List<String> res = generateParenthesis(3);

        for (String item :
                res) {
            System.out.println(item);
        }
    }
    public static List<String> generateParenthesis(int n) {
        if (n < 0){
            return null;
        }
        char[] oneRes = new char[2*n];
        int index = 0;
        List<String> res = new ArrayList<>();
        generateParen(res, n, n,oneRes,index);
        return res;
    }

    private static void generateParen(List<String> res, int leftBracket, int rightBracket, char[] oneRes, int index) {
        if (leftBracket == 0 && rightBracket == 0){
            res.add(new String(oneRes));
            return;
        }
        if (!isLegal(oneRes,index)){
            return;
        }
        if (leftBracket > 0){
            oneRes[index] = '(';
            generateParen(res,leftBracket - 1,rightBracket,oneRes,index + 1);
        }
        if (rightBracket > 0){
            oneRes[index] = ')';
            generateParen(res,leftBracket,rightBracket - 1,oneRes,index + 1);
        }
    }

    private static boolean isLegal(char[] oneRes, int index) {
        int left = 0;
        int right = 0;
        for (int i = 0;i < index;i ++){
            if (oneRes[i] == '\u0000'){
                break;
            }
            if (oneRes[i] == '('){
                left ++;
            }
            if (oneRes[i] == ')'){
                right ++;
                if (right > left){
                    return false;
                }
            }
        }
        return true;
    }
}
